package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/maximum-product-of-word-lengths/'>最大单词长度乘积(Maximum Product of Word Lengths)</a>
 * <p>给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
 *      输出：16
 *      解释：这两个单词为 "abcw", "xtfn"。
 *
 * 示例 2：
 *      输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
 *      输出：4
 *      解释：这两个单词为 "ab", "cd"。
 *
 * 示例 3：
 *      输入：words = ["a","aa","aaa","aaaa"]
 *      输出：0
 *      解释：不存在这样的两个单词。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>2 <= words.length <= 1000</li>
 *     <li>1 <= words[i].length <= 1000</li>
 *     <li>words[i] 仅包含小写字母</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/8 16:39
 */
public class LC0318MaximumProductOfWordLengths_M {

    static class Solution {
        public int maxProduct(String[] words) {
            int length = words.length;
            int[] masks = new int[length];
            for (int i = 0; i < words.length; i++) {
                String word = words[i];
                for (int j = 0; j < word.length(); j++) {
                    masks[i] |= 1 << (word.charAt(j) - 'a');
                }
            }
            int maxProd  = 0;
            for (int i = 0; i < length; i++) {
                for (int j = i+1; j < length; j++) {
                    if ((masks[i] & masks[j]) == 0) {
                        maxProd = Math.max(maxProd, words[i].length() * words[j].length());
                    }
                }
            }
            return maxProd ;
        }

        /**
         * 小优化。对于 字符相同，次数不同的字符串，只需要记录最长的字符串即可。例如：a,aa,aaa->aaa
         */
        public int maxProduct2(String[] words) {
            int length = words.length;
            int[] masks = new int[length];
            Map<Integer, Integer> mask2MaxLengthMap = new HashMap<>();
            for (String word : words) {
                // 计算每个单词的掩码。例如：abc->0000 0011  abcd-> 0000 0111    abccd->0000 0111
                int mask = 0;
                for (int j = 0; j < word.length(); j++) {
                    mask |= 1 << (word.charAt(j) - 'a');
                }
                if (word.length() > mask2MaxLengthMap.getOrDefault(mask, 0)) {
                    mask2MaxLengthMap.put(mask, word.length());
                }
            }
            int maxProduct = 0;
            for (Map.Entry<Integer, Integer> entry1 : mask2MaxLengthMap.entrySet()) {
                int mask1 = entry1.getKey();
                int maxLength1 = entry1.getValue();
                for (Map.Entry<Integer, Integer> entry2 : mask2MaxLengthMap.entrySet()) {
                    int mask2 = entry2.getKey();
                    int maxLength2 = entry2.getValue();
                    if ((mask1 & mask2) == 0) {
                        maxProduct = Math.max(maxProduct, maxLength1 *maxLength2 );
                    }
                }
            }
            return maxProduct ;
        }
    }
}
